﻿// owner 蒋家伟

#pragma once
#include <unordered_map>
#include <list>
#include <type_traits>

namespace jsdk
{
// 描述：可查询的链表, 插入与查询的时间复杂度都是O(1)
// 作用：保证插入顺序又可以根据插入的key值进行查询
// 用例：与常规的数据结构无异

    template<typename KeyType, typename ValueType, typename Hash = std::hash<KeyType>>
    class QueryableList
    {
        static_assert(!std::is_reference<KeyType>::value && !std::is_pointer<KeyType>::value, "KeyType 不能是引用或者指针");
        using Myt = typename QueryableList<KeyType, ValueType, Hash>;
        QueryableList(const Myt&) = delete;
        QueryableList& operator=(const Myt&) = delete;
    public:
        using KeyToValuePair = typename std::pair<KeyType, ValueType>;
        using QueryableListIter =typename std::list<KeyToValuePair>::iterator;
        using const_QueryableListIter = typename std::list<KeyToValuePair>::const_iterator;
        using const_reverse_QueryableListIter = typename std::list<KeyToValuePair>::const_reverse_iterator;
        using reverse_QueryableListIter = typename std::list<KeyToValuePair>::reverse_iterator;
        using size_type = typename std::list<KeyToValuePair>::size_type;
        using valueType = typename ValueType;


        QueryableList() {};

        QueryableList(Myt&& rQueryableList)
        {
            this->m_searchUMap.swap(rQueryableList.m_searchUMap);
            this->m_list.swap(rQueryableList.m_list);
        }

        ~QueryableList() {};

        bool emplace_back(const KeyType& key, const ValueType& value)
        {
            if (m_searchUMap.count(key))
                return false;
            auto listIter = m_list.insert(m_list.end(), std::make_pair(key, value));
            m_searchUMap[key] = listIter;
            return true;
        }

        bool emplace_back(const KeyType& key, ValueType&& value)
        {
            if (m_searchUMap.count(key))
                return false;
            auto listIter = m_list.insert(m_list.end(), std::make_pair(key, std::move(value)));
            m_searchUMap[key] = listIter;
            return true;
        }

        bool emplace_front(const KeyType& key, const ValueType& value)
        {
            if (m_searchUMap.count(key))
                return false;
            m_list.emplace_front(std::make_pair(key, value));
            m_searchUMap[key] = m_list.begin();
            return true;
        }

        bool emplace_front(const KeyType& key, ValueType&& value)
        {
            if (m_searchUMap.count(key))
                return false;
            m_list.emplace_front(std::make_pair(key, std::move(value)));
            m_searchUMap[key] = m_list.begin();
            return true;
        }

        std::pair<QueryableListIter, bool> insert(const QueryableListIter& iter, const KeyType& key, ValueType&& value)
        {
            if (m_searchUMap.count(key))
                return std::make_pair(iter, false);
            QueryableListIter res = m_list.insert(iter, std::make_pair(key, std::forward<ValueType>(value)));
            m_searchUMap[key] = res;
            return std::make_pair(res, true);
        }

        bool erase(const KeyType& key)
        {
            const auto& iter = m_searchUMap.find(key);
            if (iter != m_searchUMap.end())
            {
                m_list.erase(iter->second);
                m_searchUMap.erase(iter);
                return true;
            }
            return false;
        }

        QueryableListIter erase(const QueryableListIter& iter)
        {
            if (iter == m_list.end())
            {
                return m_list.end();
            }

            const auto& iterForMap = m_searchUMap.find(iter->first);
            if (iterForMap != m_searchUMap.end())
            {
                auto return_iter = m_list.erase(iter);
                m_searchUMap.erase(iterForMap);
                return return_iter;
            }

            throw "The current iterator does not belong to this container.";
            return m_list.end();
        }

        const_QueryableListIter cbegin() const
        {
            return m_list.cbegin();
        }

        const_QueryableListIter cend() const
        {
            return m_list.cend();
        }

        QueryableListIter begin()
        {
            return m_list.begin();
        }

        const_QueryableListIter begin() const
        {
            return m_list.begin();
        }

        QueryableListIter end()
        {
            return m_list.end();
        }

        const_QueryableListIter end() const
        {
            return m_list.end();
        }

        const_reverse_QueryableListIter crbegin() const
        {
            return m_list.crbegin();
        }

        const_reverse_QueryableListIter crend() const
        {
            return m_list.crend();
        }

        reverse_QueryableListIter rbegin()
        {
            return m_list.rbegin();
        }

        reverse_QueryableListIter rend()
        {
            return m_list.rend();
        }

        const_QueryableListIter find(const KeyType& key) const
        {
            const auto& iter = m_searchUMap.find(key);
            if (iter != m_searchUMap.end())
            {
                return iter->second;
            }
            return m_list.cend();
        }

        QueryableListIter find(const KeyType& key)
        {
            const auto& iter = m_searchUMap.find(key);
            if (iter != m_searchUMap.end())
            {
                return iter->second;
            }
            return m_list.end();
        }

        size_type size() const
        {
            if (m_list.size() != m_searchUMap.size())
            {
                throw "list' size is equal map'size";
            }
            return m_list.size();
        }

        bool empty() const 
        {
            return size() == 0;
        }

        void clear()
        {
            m_searchUMap.swap(std::unordered_map<KeyType, QueryableListIter, Hash>{});
            m_list.swap(std::list<KeyToValuePair>{});
        }

        ValueType popValue(const KeyType& key)
        {
            auto& iter = m_searchUMap.find(key);
            if (iter != m_searchUMap.end())
            {
                ValueType temp = std::move(iter->second->second);
                this->erase(key);
                return std::move(temp);
            }
            else
            {
                // 
                throw "The current key does not belong to this container";
                return ValueType{};
            }
        }

        void swap(QueryableList<KeyType, ValueType, Hash>& rQueryableList)
        {
            this->m_searchUMap.swap(rQueryableList.m_searchUMap);
            this->m_list.swap(rQueryableList.m_list);
        }

    private:


    private:
        std::unordered_map<KeyType, QueryableListIter, Hash> m_searchUMap;
        std::list<KeyToValuePair> m_list;
    };
}